package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
		Reverse a singly linked list.
	
	click to show more hints.
	
	Hint:
	A linked list can be reversed either iteratively or recursively. Could you implement both?
		
题目大意

	　　反转单链表。 
	
解题思路
	      
	       使用头插法。 
		
 * @Date 2017-09-14 22：39
 */
public class _206_Reverse_Linked_List {
	public static class ListNode {
		int val;
		ListNode next = null;
		ListNode(int x) {
			val = x;

		}
	}
	
	private ListNode newLinkList1() {
		ListNode root = new ListNode(1);
		root.next = new ListNode(2);
		root.next.next = new ListNode(3);
		root.next.next.next = new ListNode(4);
		root.next.next.next.next = new ListNode(5);
		return root;
	}
	
	/**
	 * 反转链表： 头插法
	 * @My
	 * @param head
	 * @return
	 */
    public ListNode reverseList(ListNode head) {
    	if (head == null)	return null;
    	//p:遍历原链表, root:新链表头
    	ListNode p = head, root = null;	
    	while (p != null) {
    		//pNew新链表的新创建节点
    		ListNode pNew = new ListNode(p.val);
    		pNew.next = root;
    		root = pNew;
    		p = p.next;
    	}
//    	traverse(root);
		return root;
    }
	
	/**
	 * 反转链表：  
	 * @My
	 * @param head
	 * @return
	 */
    public ListNode reverseList2(ListNode head) {
	    if (head == null)	return null;
		ListNode p = head, q = p.next;
		ListNode temp = q;
		p.next = null;
	
		while (q != null) {
			temp = q.next;
			q.next = p;
			p = q;
			q = temp;
		}
	//	ListNode.traverse("reverse结果", p);
 	return p;
}
    
    
    public void traverse(ListNode root) {
    	ListNode p = root;
    	while (p != null) {
    		LogUtils.print(p.val);
    		p = p.next;
    	}
    }
 	
	public static void main(String[] args) {
		_206_Reverse_Linked_List obj = new _206_Reverse_Linked_List();
		obj.reverseList(obj.newLinkList1());
	}

}
